package 第三周;

/*
 * @author  YxinMiracle
 * @date  2022-04-28 10:04
 * @Gitee: https://gitee.com/yxinmiracle
 */

import javafx.util.Pair;

public class 二叉树的最近公共祖先 {

    TreeNode p, q; // 需要找到的点
    TreeNode ans; // 答案

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.p = p;
        this.q = q;
        dfs(root);
        return ans;
    }

    private Pair<Boolean, Boolean> dfs(TreeNode root) {
        if (root == null){
            return new Pair<>(false,false);
        }
        Pair<Boolean,Boolean> treeLeftResult = dfs(root.left);
        Pair<Boolean,Boolean> treeRightResult = dfs(root.right);
        Pair<Boolean,Boolean> result = new Pair<>(
                treeLeftResult.getKey() || treeRightResult.getKey() || root.val == p.val ,
                treeLeftResult.getValue() || treeRightResult.getValue() || root.val == q.val
        );
        if (result.getKey() && result.getValue() && ans == null) ans = root;
        return result;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        System.out.println(new 二叉树的最近公共祖先().lowestCommonAncestor(treeNode, new TreeNode(1), new TreeNode(2)));
    }
}
